package william.array;

/**
 * @author ZhangShenao
 * @date 2024/2/28
 * @description <a href="https://leetcode.cn/problems/remove-element/">...</a>
 */
public class Leetcode27_移除元素 {
    /**
     * 采用双指针法
     * 指针i用于遍历数组,指针lastNonVal指向最后一个非val的元素,[0...lastNonVal)范围内的元素均!=val。lastNonVal从0开始
     * 遍历数组,如果当前元素!=val,则将当前元素与lastNonVal位置的元素交换,并将lastNonVal+1
     * 最终返回lastNonVal即为移除后数组的长度
     * <p>
     * 时间复杂度O(N) 只遍历一次数组
     * 空间复杂度O(1)
     */
    public int removeElement(int[] nums, int val) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            return 0;
        }

        //双指针法
        //指针lastNonVal用于记录最后一个!=val的元素下标
        //指针i用于遍历数组
        int lastNonVal = 0;

        //遍历数组,如果当前元素!=val,则将当前元素与lastNonVal位置的元素交换,并将lastNonVal+1
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                if (i != lastNonVal) {
                    swap(nums, i, lastNonVal++);
                } else {
                    lastNonVal++;
                }
            }
        }

        //最后返回lastNonVal即为非val的元素数量
        return lastNonVal;

    }

    /**
     * 交换数组i,j两个位置的元素
     */
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
